from functools import cache
from typing import List

# 方法一： 记忆化搜索
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:

        m = len(grid)
        n = len(grid[0])

        @cache
        def dfs(i, j):

            if i == m - 1 and j == n - 1:
                return grid[i][j]

            # 越界，返回最大的，不选他
            if i >= m or j >= n:
                return float('inf')
            return min(dfs(i + 1, j) + grid[i][j], dfs(i, j + 1) + grid[i][j])

        return dfs(0, 0)

# 方法二： 动态规划
from typing import List


class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m = len(grid)
        n = len(grid[0])

        dp = [[0] * n for _ in range(m)]
        dp[0][0] = grid[0][0]

        # 初始化第一行，因为不初始化dp[i-1][j] 当前i为0时，dp[i-1][j]为0，会导致错误，
        for j in range(1, n):
            dp[0][j] = dp[0][j - 1] + grid[0][j]

        # 初始化第一列
        for i in range(1, m):
            dp[i][0] = dp[i - 1][0] + grid[i][0]

        # 填充其余部分
        for i in range(1, m):
            for j in range(1, n):
                # dp考虑的是下一个状态的置， 当前状态grid[i][j]都加，不影响
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

        return dp[m - 1][n - 1]